package com.zhzh.sc.demo.leetcode.easy;

import java.util.*;
import java.util.stream.Collectors;

/**
 ### [1481\. Least Number of Unique Integers after K Removals](https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/)

 Difficulty: **Medium**

 Related Topics: [Array](https://leetcode.com/tag/array/), [Sort](https://leetcode.com/tag/sort/)


 Given an array of integers `arr` and an integer `k`. Find the _least number of unique integers_ after removing **exactly** `k` elements**.**

 **Example 1:**

 ```
 Input: arr = [5,5,4], k = 1
 Output: 1
 Explanation: Remove the single 4, only 5 is left.
 ```

 **Example 2:**

 ```
 Input: arr = [4,3,1,1,3,3,2], k = 3
 Output: 2
 Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
 ```

 **Constraints:**

 *   `1 <= arr.length <= 10^5`
 *   `1 <= arr[i] <= 10^9`
 *   `0 <= k <= arr.length`


 #### Solution

 Language: **Java**

 ```java
 class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> arrMap = new HashMap();
        for (int i : arr) {
            arrMap.merge(i, 1, Integer::sum);
        }
        List<Integer> valueList = arrMap.entrySet().stream().sorted((Map.Entry.comparingByValue())).map(Map.Entry::getValue).collect(Collectors.toList());
        System.out.println(valueList);
        Iterator<Integer> iterator = valueList.iterator();
        int sum = 0;
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (k > 0 && k >= next) {
                k = k - next;
                iterator.remove();
            } else {
                sum++;
            }
        }
        return sum;
    }
 }
 ```
 */

/**
 * @author: dasouche
 * @date: 2021-03-24 16:54
 **/
public class LeastNumberOfUniqueIntegersAfterKRemovals {

    public static void main(String[] args) {
        int leastNumOfUniqueInts = findLeastNumOfUniqueInts(new int[]{5, 5, 4}, 1);
        System.out.println(leastNumOfUniqueInts);
    }

    public static int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> arrMap = new HashMap();
        for (int i : arr) {
            arrMap.merge(i, 1, Integer::sum);
        }
        List<Integer> valueList = arrMap.entrySet().stream().sorted((Map.Entry.comparingByValue())).map(Map.Entry::getValue).collect(Collectors.toList());
        System.out.println(valueList);
        Iterator<Integer> iterator = valueList.iterator();
        int sum = 0;
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (k > 0 && k >= next) {
                k = k - next;
                iterator.remove();
            } else {
                sum++;
            }
        }
        return sum;
    }
}
